import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Scanner;

public class kmp {

    public static void main(String[] args) throws Exception{
        String fileName = "D:/test.txt";
        FileReader fileReader = new FileReader(fileName);
        BufferedReader bufferedReader = new BufferedReader(fileReader);  //提高文件读取速率，对文件进行缓冲,并且它具有readLine()方法
        ArrayList<String> list = new ArrayList();
        String line = bufferedReader.readLine();
        while (line != null){
            list.add(line);
            line = bufferedReader.readLine();
        }
        for (String s : list){
            System.out.println(s);
        }
        System.out.print("请输入要匹配的字符串：");
        Scanner sc = new Scanner(System.in);
        String childStr = sc.next();
        int i = 0;
        boolean flag = false;
        while(i < list.size()){
            for (int j = 0 ;j < kmpSearch(list.get(i),childStr,getNext(childStr)).size(); j++){
                System.out.println("匹配的字符串位于第"+i+"行第"+kmpSearch(list.get(i),childStr,getNext(childStr)).get(j)+"列");
                flag = true;
            }
            i++;
        }
        if(flag == false){
                System.out.println("未匹配到该子串");
        }
        bufferedReader.close();
        fileReader.close();
    }
    public static ArrayList<Integer> kmpSearch(String str, String childStr, int[] next){//str文本串  childStr 模式串
        ArrayList<Integer> array = new ArrayList();
        for(int i = 0, j = 0; i < str.length(); i++){
            while(j > 0 && str.charAt(i) != childStr.charAt(j)){
                j = next[j - 1];
            }
            if(str.charAt(i) == childStr.charAt(j)){
                j++;
            }
            if(j == childStr.length()){
                array.add(i-j+1);
                j = 0;
            }
        }
        return array;
    }
    public static int[] getNext(String str){
        int[] next = new int[str.length()];
//        next[0] = 0;
//        for(int i = 1,j = 0; i < str.length(); i++){
//            while(j > 0 && str.charAt(j) != str.charAt(i)){
//                j = next[j - 1];
//            }
//            if(str.charAt(i) == str.charAt(j)){
//                j++;
//            }
//            next[i] = j;
//        }
        next[0] = -1;
        int k = -1;
        int i = 0;
        while (i < str.length()-1){
            if(k == -1 || str.charAt(k) == str.charAt(i)){
                k++;
                i++;
                next[i] = k;
            }else{
                k = next[k];
            }
        }
        next[0] = 0;
        return next;
    }
}


